// leetcode.algorithms.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <stack>
#include <queue>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>

using namespace std;

class sq_solution
{
public:
  template<typename T>
  int removeDuplicate(std::vector<T>& vec)
  {
    return distance(vec.begin(), unique(vec.begin(), vec.end()));
  }

  int removeDuplicateNoMoreThanOne(std::vector<int>& vec)
  {
    if (vec.empty()) return 0;
    int index = 0;
    for (int i = 1; i < vec.size(); i++)
    {
      if (vec[index] != vec[i])
        vec[++index] = vec[i];
    }

    return index + 1;
  }

  bool containsDuplicate(vector<int>& nums) {
    unordered_map<int, int> cnt;
    for (auto i : nums)
    {
      if (cnt.find(i) != cnt.end())
      {
        return true;
      }
      else
      {
        cnt[i] = 1;
      }
    }

    return false;
  }

  void reverse(vector<int>& nums, int start, int end) {
    while (start < end)
    {
      swap(nums[start], nums[end]);
      end--;
      start++;
    }
  }

  void rotateFast(vector<int>& nums, int k) {
    k %= nums.size();
    reverse(nums, 0, nums.size() - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.size() - 1);
  }

  void rotate(vector<int>& nums, int k) {
    int n = nums.size();
    vector<int> new_arr(n);
    for (int i = 0; i < n; i++)
      new_arr[(i + k) % n] = nums[i];
    nums.assign(new_arr.begin(), new_arr.end());
  }

  void moveZeroes(vector<int>& nums) {
    int end = nums.size();
    for (int i = 0; i < end; i++) {
      if (nums[i] == 0) {
        for (int j = i; j < end - 1; j++) {
          swap(nums[j], nums[j + 1]);
        }
        end--;
        i--;
      }
    }
  }

  //nums1 = [2,7,11,15], nums2 = [2,7]
  vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
    vector<int> res;
    unordered_map<int, int> cnt;

    for (auto i : nums1)
    {
      if (cnt.find(i) != cnt.end())
        cnt[i]++;
      else
        cnt[i] = 1;
    }

    for (auto i : nums2)
    {
      if (cnt.find(i) != cnt.end())
      {
        res.push_back(i);
        cnt[i]--;
        if (cnt[i] == 0)
          cnt.erase(i);
      }
    }
    return res;
  }

  void rotate(vector<vector<int>>& matrix) {
    int rows = matrix.size() - 1;
    int cols = matrix[0].size();
    int start = 0, iend = rows;
    for (int irow = 0; irow < iend; irow++, iend--) {
      for (int icol = 0; icol < cols; icol++) {
        swap(matrix[irow][icol], matrix[iend][icol]);
      }
    }

    for (int i = 0; i < rows; i++) {
      for (int j = i; j < cols; j++) {
        if (i != j) {
          swap(matrix[j][i], matrix[i][j]);
        }
      }
    }
  }

  int singleNumber(vector<int>& nums) {
    if (nums.size() == 1) return nums[0];
    unordered_map<int, int> cnt;
    for (auto i : nums)
    {
      if (cnt.find(i) != cnt.end())
      {
        cnt[i]++;
      }
      else
      {
        cnt[i] = 1;
      }
    }

    for (auto i : cnt)
    {
      if (i.second == 1)
        return i.first;
    }
  }

  int removeDuplicateNoMoreThanTwo(std::vector<int>& vec)
  {
    if (vec.size() <= 2) return vec.size();
    int index = 2;
    for (int i = 2; i < vec.size(); i++)
    {
      if (vec[index - 2] != vec[i])
        vec[index++] = vec[i];
    }

    return index + 1;
  }

  /// <summary>
  /// 100 3 200 1 2 4 should return 4
  /// </summary>
  /// <param name="nums"></param>
  /// <returns></returns>
  int longestConsecutive(const vector<int>& nums)
  {
    unordered_map<int, bool> used;
    for (auto i : nums) used[i] = false;

    int longest = 0;

    for (auto i : nums)
    {
      if (used[i]) continue;
      int length = 1;
      used[i] = true;
      for (int j = i + 1; used.find(j) != used.end(); ++j)
      {
        used[j] = true;
        length++;
      }

      for (int j = i - 1; used.find(j) != used.end(); --j)
      {
        used[j] = true;
        length++;
      }
      longest = max(longest, length);
    }
    return longest;
  }

  /// <summary>
  /// 2 7 11 15, 13
  /// </summary>
  /// <returns></returns>
  vector<int> TwoSum(vector<int>& nums, int target)
  {
    unordered_map<int, int> used;
    vector<int> results;
    int idx = 0;
    for (auto i : nums) used[i] = idx++;
    idx = 0;
    for (auto i : nums)
    {
      if (used.find(target - i) != used.end() && used[target - i] > idx)
      {
        results.push_back(idx + 1);
        results.push_back(used[target - i] + 1);
        break;
      }
      idx++;
    }
    return results;
  }
};